Masala #0744

Sizga \(N\) ta har xil natural sonlardan tashkil topgan \(A\) to’plam berilgan. Siz to’plamda yagona son qolgunga qadar quyidagi amallardan birini qilishingiz kerak:

• To’plamdan \(\text{birlarSoni}(Ai⊕Aj)=1\) shartni qanoatlantiradigan ikkita sonni tanlab ulardan ixtiyoriy birini(yoki \(Ai\), yoki \(A_j\)) ni to’plamdan o’chirishingiz mumkin. Buning uchun \(E_1\) energiya sarflaysiz.
• To’plamdan \(\text{birlarSoni}(Ai⊕Aj)>1\) shartni qanoatlantiradigan ikkita sonni tanlab ulardan ixtiyoriy birini(yoki \(A_i\), yoki \(A_j\)) ni to’plamdan o’chirishingiz mumkin. Buning uchun \(E_2\) energiya sarflaysiz.

Bu yerda \(⊕\) bitwise XOR amali, \(\text{birlarSoni}(X)\) esa \(X\) sonining ikkilik sanoq tizimida yozilishidagi birlar sonini qaytaradi.

Siz to’plamda yagona son qolgunga qadar bu amallarni bajarish uchun eng kamida qancha energiya sarflanishini aniqlang

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 20)\) testlar soni kiritiladi. Keyingi satrdan boshlab har bir testning 1-satrida bitta butun son, \(N (1 \le N \le 10000)\) \(A\) to’plam elementlari soni, 2-satrida ikkita butun son, \(E_1\) hamda \(E_2 (1 \le E_1, E_2 \le 10^9)\) sonlari kiritiladi, 3-satrda N ta butun son, \(A (1 \le A_i \le 10^9)\) to’plam elementlari kiritiladi.

Chiqish faylida har bir test uchun alohida qatorda \(A\) to’plamda yagona son qolgunga qadar o’chirish amallarini bajarish uchun eng kamida qancha energiya sarflanishini chop eting.